|
|
Undecidability of Some Substructural Logics
Chvalovský, Karel ; Bílková, Marta (vedoucí práce) ; Buszkowski, Vojciech (oponent) ; Galatos, Nick (oponent)
Tato disertační práce se zabývá algoritmickou nerozhodnutelností (neřešitel- ností) dokazatelnosti v některých neklasických logikách. Ve skutečnosti existují dvě přirozené varianty toho problému. Mějme dánu logiku, pak můžeme studovat její množinu teorémů nebo její relaci důsledku, což je obecnější problém. Je známo, že oba tyto problémy mohou být nerozhod- nutelné již pro výrokové logiky a tato disertační práce poskytuje další pří- klady takových logik. Konkrétně se věnujeme výrokovým substrukturálním logikám, které lze získat ze sekventového kalkulu LJ pro intuicionistickou logiku odebráním strukturálních pravidel. Naše hlavní výsledky jsou násle- dující. Ukazujeme nerozhodnutelnost (konečné) relace důsledku pro některé základní neasociativní substrukturální logiky. Dále dokazujeme, že množina teorémů v základní substrukturální logice s pravidlem kontrakce, které ob- vykle způsobuje řadu komplikací, je nerozhodnutelná. Neboť studované logiky mají přirozené algebraické sémantiky, dostáváme také odpovídající algebraické výsledky, které jsou zajímavé samy o sobě.
|
|
|
Logical background of forcing
Glivická, Jana ; Honzík, Radek (vedoucí práce) ; Chodounský, David (oponent)
V předložené práci zkoumáme forcing jako metodu teorie množin a zaměřu- jeme se na okolnosti, které jsou při obvyklých výkladech a aplikacích forcingu ponechávány stranou. Ukážeme, že forcing lze formalizovat v Peanově aritmetice (PA) a že výsledky o relativních konzistencích teorií získané pomocí forcingu jsou dokazatelné v PA. Předvedeme dva způsoby, jak je možné překonat předpoklad existence spočetného tranzitivního modelu. Studujeme také forcing jako metodu, na jejímž základě je možné konstruovat interpretace teorií v teoriích jiných. Zavádíme pojem bi-interpretace a budujeme metodu forcingu přes nestandardní model ZFC, pomocí níž ukážeme, že teorie ZFC a ZF nejsou bi-interpretovatelné. 1
|
host ::
RSS.